from collections import OrderedDict
from copy import deepcopy

dp_matrix = OrderedDict()

def merge_matrices(*matrices):
    # 确保所有矩阵的行数相同
    row_lengths = set(len(matrix) for matrix in matrices)
    # assert len(row_lengths) == 1, "所有矩阵的行数不相同"

    merged_matrix = [sum(rows, []) for rows in zip(*matrices)]
    return merged_matrix

def knapsack(items, capacity):
    # items: 物品列表，每个物品表示为 (weight, value) 的元组
    # capacity: 背包的容量
    
    n = len(items)
    
    # 创建二维数组dp，用于存储状态
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    # 动态规划求解最优解
    for i in range(1, n + 1):
        item_weight, item_value = items[i - 1]
        for j in range(1, capacity + 1):
            current_capacity = j

            if item_weight > current_capacity:
                # 当前物品的重量大于背包当前容量，无法放入该物品,
                # 最大总价值与前i-1个物品时的最大总价值相同
                previous_max_value = dp[i - 1][current_capacity]
                dp[i][current_capacity] = previous_max_value
            else:
                # 可以选择放入或不放入当前物品，选择较大的值作为当前状态的最优解
                remaining_capacity = current_capacity - item_weight
                remaining_max_value = dp[i - 1][remaining_capacity]
                current_max_value = max(remaining_max_value + item_value,
                                        dp[i - 1][current_capacity])
                dp[i][current_capacity] = current_max_value

            dp_matrix.update([(f'dp[{i}][{j}]', deepcopy(dp))])


    # 回溯得到最优解的物品集合
    selected_items = []
    current_capacity = capacity
    for i in range(n, 0, -1):
        if dp[i][current_capacity] != dp[i - 1][current_capacity]:
            item = items[i - 1]
            selected_items.append(item)
            current_capacity -= item[0]
    
    # 返回放入背包的物品集合和对应的最大总价值
    return selected_items[::-1], dp[n][capacity]

def format_line(keys, start_index, end_index, width, spaces, matrix_interval):
    line = ""
    for i in range(start_index, end_index):
        matrix_name = keys[i]
        line += matrix_interval[len(matrix_name):] + matrix_name
        if i != end_index - 1:
            line += spaces
    return line

if __name__ == "__main__":
    # 物品列表，每个物品表示为 (weight, value) 的元组
    items = [(2, 6), (2, 10), (3, 12), (4, 10), (3, 14)]
    n = len(items)
    
    # 背包的容量
    capacity = 5
    
    # 使用动态规划求解背包问题
    selected_items, max_value = knapsack(items, capacity)
    
    # 输出放入背包的物品和最大总价值
    print("物品列表:", items)
    print("背包容量:", capacity)
    print("放入背包的物品:", selected_items)
    print("最大总价值:", max_value)

    width = 3
    spaces = " " * 8
    matrix_interval = ' ' *  width * (capacity+1)
    matrix_interval_len = len(matrix_interval)
    keys = list(dp_matrix.keys())
    for i in range(0, len(keys), capacity):
        line = format_line(keys, i, i + capacity, width, spaces, matrix_interval)
        print(line)
        for idx, row in enumerate(merge_matrices(*list(dp_matrix.values())[i : i + capacity])):
            # 分割行数据并按间隔插入制表符
            new_row = [row[k:k+capacity+1] for k in range(0, len(row), capacity+1)]
            merged_row = f"{spaces}".join(''.join(f'{elem:-{width}}' for elem in sub_row) for sub_row in new_row)
            print(merged_row)
        print()
